1. Technical Field
This disclosure relates generally to trimming of polygon data.
2. Background Information
A map is a representation of geographic data, for example data that represents regions or features on a planet's surface, such as the Earth's surface. Geographic data specifies features in relation to geographic measure (i.e. georeferences the features) in 3-dimensional space, for example in relation to latitude (parallels) and longitude (meridians). Latitude is defined formally as the angle between the plane of the equator of a planet and a line normal to an idealized surface connecting a point in question to the planet's rotational axis. Longitude is defined formally as the angle at the center of a planet between two planes that align with, and intersect along, the axis of rotation, perpendicular to the plane of the equator. One plane contains the Prime Meridian and the other contains the point in question.
To display a map on a two-dimensional medium, such as a piece of paper, or a computer screen, it is often desirable to convert geographic coordinates to projected coordinates in a transformation process commonly referred to as map projection. In this manner, a two-dimensional representation is created from three-dimensional data. With all map projections, certain properties of the data are preserved, while other properties may be distorted or approximated to facilitate the projection. Depending on the particular type of map projection employed, area, distance (along certain lines), direction, local shape or other properties may be preserved or distorted. A large number of different map projections are known and used in the art. Many of these projections are classified into three large categories of projections. A first category of map projections is commonly termed cylindrical map projections. Cylindrical map projections are produced by mathematically modeling a cylinder about a sphere having the geographic coordinates laid thereon and projecting these coordinates onto the cylinder's interior surface. The cylinder is then unwrapped to yield a flat map. Cylindrical map projections may be equal-area (i.e. preservative of area of regions), conformal (i.e. preservative of angles between features), equidistant (i.e. preservative of distance along selected curves) or otherwise configured, depending on the techniques used to create the projection.
A second category of map projections is commonly termed conical map projections. Conical map projections are produced by mathematically modeling a cone placed about a sphere having the geographic coordinates laid thereon, and projecting these coordinates onto the cone's interior surface. This surface is then unwrapped. Conical map projections often achieve less distortion at middle and high latitudes than cylindrical map projections, yet trade-off other qualities to achieve this advantage.
A third category of map projections is commonly termed azimuthal map projections. Azimuthal map projections are produced by mathematically modeling a plane tangent or proximate to a sphere having the geographic coordinates laid thereon, and projecting the geographic coordinates onto the plane. When the tangent point is selected as a pole of a planet, the projection is commonly termed a polar azimuthal map projection. In a conventional polar azimuthal map projection, meridians are projected as straight lines radiating from the pole, and parallels are projected as complete circles centered at the pole. Most azimuthal map projections are not suitable for displaying all of a planet in one projection, and accordingly two or more azimuthal map projections are often employed to represent an entire planet.
Sometimes it is desirable to create a map of a specific region, using only certain portions of the geographic data available, rather than all the available geographic data. For example, one may desire a map of a quadrangle of the surface of a planet, i.e. a region bounded by parallels (or possibly a pole) north and south, and meridians east and west. When only a selected quadrangle is to be mapped, geographic data must be “trimmed” at the boundaries of the quadrangle, so as to limit the features mapped to those in the quadrangle. This often presents technical challenges.
Geographic data may be represented in a variety of manners. In many systems, geographic data takes the form of vectors, i.e. arrays with storage locations accessible by reference to an integer offset. Separate vectors may be employed for latitude and longitude data, with corresponding elements from the two vectors representing the coordinates of points. For example, a simple set of vector geographic data may be:lat=[45.6 −23.47 78];lon=[13 −97.45 165];where the coordinates (in degrees latitude and longitude) of three points are provided.
Depending on the context, vector data may describe individual points (for example, referring to the above data, three individual points), line segments (for example, referring the above data, two line segments joined at a point), or vertices of polygons (for example, referring the above data, the three vertices of a triangle).
Polygons are figures having three or more faces (i.e. sides) that form a ring (i.e. a simple closed curve). A set of geographic data may specify a large number of polygons. A polygon that is intended to enclose a region (for example, to enclose a continent or other landmass) is commonly characterized as an outer ring, while a polygon that exists inside of an outer ring, and is intended to exclude an area, i.e. to create a “hole” (for example, to represent a lake or an inland sea) is commonly termed an inner ring. Generally outer rings and inner rings may not intersect, except possibly at a single tangent point.
When geographic data takes the form of polygons, and the geographic data is trimmed at the boundaries of a quadrangle, individual polygons that extend across the boundaries of the quadrangle generally must also be trimmed. That is, the boundaries of the individual polygons must be modified so as to not extend beyond the quadrangle, while still representing a closed figure. Polygon trimming presents various technical challenges which have not been adequately addressed in prior systems.
For example, in many prior systems longitude wrapping proves problematic to polygon trimming and may lead to unacceptable results. Longitude wrapping is a condition that may exist due to longitude “wrapping around the planet,” such that the same point, or nearby points, are represented by quite different longitude coordinates, for example by coordinates which vary by multiples of 360° (or 2π radians). While all longitude coordinates may readily be converted to a standard interval, for example so that all longitude coordinates fall in the interval −180° to 180° (or −π to π radians), problemsome discontinuities may be introduced by such conversion, as information descriptive of the polygons may be lost. Prior techniques for trimming polygons to quadrangles have often inadequately and/or inelegantly accounted for such discontinuities, leading to inefficient polygon trimming, and in some systems artifacts and other irregularities in maps generated from trimmed polygon data.
Accordingly, improved techniques are needed.